#define _CRT_SECURE_NO_WARNINGS 1

#include<iostream>
#include<vector>

using namespace std;

vector<string> generateParenthesis(int n) {
    int m = 2 * n;
    vector<string> res;
    string t(m, 0);

    auto dfs = [&](auto&& dfs, int i, int l) {
        if (i == m)
        {
            res.push_back(t);
            return;
        }

        if (l < n)
        {
            t[i] = '(';
            dfs(dfs, i + 1, l + 1);
        }
        if (i - l < l)
        {
            t[i] = ')';
            dfs(dfs, i + 1, l);
        }
    };
    dfs(dfs, 0, 0);
    return res;
}

typedef pair<int, int> PII;
class Solution {
public:
    bool exist(vector<vector<char>>& board, string word) {
        n = board.size(), m = board[0].size();
        for (int i = 0; i < n; i++)
            for (int j = 0; j < m; j++)
                if (board[i][j] == word[0])
                    if (dfs({ i,j }, 0, board, word))
                        return true;

        return false;
    }

    bool dfs(PII t, int pos, vector<vector<char>>& board, string word)
    {
        int x = t.first, y = t.second;
        if (x < 0 || x >= n || y < 0 || y >= m)  return false;
        if (board[x][y] != word[pos])    return false;
        if (pos == word.size() - 1)    return true;
        board[x][y] = '\0';
        if (dfs({ x + 1,y }, pos + 1, board, word))   return true;
        if (dfs({ x - 1,y }, pos + 1, board, word))   return true;
        if (dfs({ x,y + 1 }, pos + 1, board, word))   return true;
        if (dfs({ x,y - 1 }, pos + 1, board, word))   return true;
        board[x][y] = word[pos];
        return false;
    }
    int n, m;
};